#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* twoSum(int* nums, int numsSize, int target);
int* recursiveCheck(int* nums, int numsSize, int targetRemains, int baseIndex, int level);

int main(){
    int nums[] = {-1,-2,-3,-4,-5};
    int numsSize = sizeof(nums)/sizeof(int);
    int target = -8;
    int* idxs = twoSum(nums, numsSize, target);
    int i;
    for(i = 0; i < 2; ++i)
        printf("%d  ", idxs[i]);
    printf("\n");
    free(idxs);
    return 0;
}

int* twoSum(int* nums, int numsSize, int target) {
    int i, j;
    int* twoIdx = malloc(2*sizeof(int));
    for(i = 0; i < numsSize; ++i){
        for(j = i+1; j < numsSize; ++j){
            if(nums[i] + nums[j] == target){
                twoIdx[0] = i;
                twoIdx[1] = j;
            }
        }
    }
    return twoIdx;
//    return recursiveCheck(nums, numsSize, target, 0, 0);
}

int* recursiveCheck(int* nums, int numsSize, int targetRemains, int baseIndex, int level){
    int* idxArray = NULL;
    int i;
    for(i = 0; i < numsSize; ++i){
        if(targetRemains == nums[i]){
            int* tmpArray = malloc((numsSize-i)*sizeof(int));
            int tmpIdx = i+1;
            int zeroNum = 0;
            while(tmpIdx < numsSize){
                if(nums[tmpIdx] == 0)
                    tmpArray[zeroNum++] = tmpIdx;
                ++tmpIdx;
            }
            idxArray = malloc((level+zeroNum+1)*sizeof(int));
            idxArray[level] = baseIndex+i;
            memcpy(idxArray+level+1, tmpArray, zeroNum*sizeof(int));
            free(tmpArray);
            return idxArray;
        }
        printf("targetRemains %d  \n", targetRemains);
        idxArray = recursiveCheck(nums+(i+1), numsSize-(i+1), targetRemains-nums[i], baseIndex+(i+1), level+1);
        if(idxArray != NULL){
            idxArray[level] = baseIndex+i;
            return idxArray;
        }
    }
    return idxArray;
}